package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: xiaomi
 * @date: 2021/1/9
 * @description: 123. 买卖股票的最佳时机 III
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 * 太难了，先收藏了
 */
public class C_123_买卖股票的最佳时机_III {

	static C_123_买卖股票的最佳时机_III action = new C_123_买卖股票的最佳时机_III();

	public static void main(String[] args) {
		//test1();
		test2();
	}

	public static void test1() {
		// 6
		int[] prices = new int[]{3, 3, 5, 0, 0, 3, 1, 4};
		int res = action.maxProfit(prices);
		System.out.println("res = " + res);
	}

	public static void test2() {
		// 4
		int[] prices = new int[]{1, 2, 3, 4, 5};
		int res = action.maxProfit(prices);
		System.out.println("res = " + res);
	}


	/**
	 * dp[i][j] 第 i 天的状态的最大收入
	 * 状态描述：
	 * dp[i][0]：不操作
	 * dp[i][1]：第一次买入
	 * dp[i][2]：第一次卖出
	 * dp[i][3]：第二次买入
	 * dp[i][4]：第二次卖出
	 * 确定状态转移方程：
	 * dp[i][0] = 0;
	 * dp[i][1]（保留上一次买入 or 本次买入） = max(dp[i-1][1], -prices[i])
	 * dp[i][2]（保留上一次卖出 or 本次卖出） = max(dp[i-1][2], dp[i-1][1]+prices[i])
	 * dp[i][3]（保留上一次二次买入 or 本次买入） = max(dp[i-1][3], dp[i-1][2]-prices[i])
	 * dp[i][4]（保留上一次二次卖出 or 本次卖出） = max(dp[i-1][4], dp[i-1][3]+prices[i])
	 * 但是我还是想不懂
	 * dp[0][3] = -prices[0] ????
	 * 状态转移方程是没有问题的，如果：
	 * dp[i][3]：第一次/第二次买入
	 * dp[i][4]：第一次/第二次卖出
	 * 那么最后的结果 return dp[len - 1][4]; 也就顺理成章了！
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {
		int len = prices.length;
		int[][] dp = new int[len][5];
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		dp[0][2] = 0;
		//如果 dp[0][3] = 0，会导致 dp[i][4] 的值产生偏差！
		dp[0][3] = dp[0][1];
		dp[0][4] = 0;
		for (int i = 1; i < len; i++) {
			dp[i][0] = 0;
			dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
			dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
			dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
			dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
		}
		//return Math.max(dp[len - 1][2], dp[len - 1][4]);
		return dp[len - 1][4];
	}


}
